526. 优美的排列

Similar Question

Solution Tips

方案一: 回溯

我们可以使用回溯法解决本题，从左向右依次向目标排列中放入数即可。

具体地，我们定义函数 backtrack(index,n), 表示尝试向位置 index 放入数。其中 n 表示排列的长度。在当前函数中，我们首先找到一个符合条件的未被使用过的数，然后递归地执行 backtrack(index+1,n)，当该函数执行完毕，回溯到当前层，我们再尝试下一个符合条件的未被使用过的数即可。

回溯过程中，我们可以用 vis 数组标记哪些数被使用过，每次我们选中一个数 x，我们就将 vis[x] 标记为 true，回溯完成后，我们再将其置为 false。

特别地，为了优化回溯效率，我们可以预处理每个位置的符合条件的数有哪些，用二维数组 match 保存。当我们尝试向位置 index 放入数时，我们只需要遍历

match[index] 即可。

var countArrangement = function(n) {
    const vis = new Array(n + 1).fill(0);
    const match = new Array(n + 1).fill(0);
    let num = 0;
    for (let i = 0; i <= n; i++) {
        match[i] = [];
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            if (i % j === 0 || j % i === 0) {
                match[i].push(j);
            }
        }
    }
	
    const backtrack = (index, n) => {
        if (index === n + 1) {
            num++;
            return;
        }
        for (const x of match[index]) {
            if (!vis[x]) {
                vis[x] = true;
                backtrack(index + 1, n);
                vis[x] = false;
            }
        }
    }
    
    backtrack(1, n);
    return num;
};

方法二: 状态压缩 + 动态规划

526. 优美的排列 题解 - 力扣（LeetCode）